\documentclass[12pt, a4paper]{article}

\usepackage{sbc-template}

\usepackage{graphicx,url}

\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage[boxruled,linesnumbered,portuguese]{algorithm2e}
\usepackage{pdfpages}

\newcommand{\Halite}{{\em{Halite}}}
\newcommand{\Haliteds}{{\em{Halite$_{ds}$}}}
\newcommand{\tree}{{\em{Árvore de Contagens}}}


\begin{document}

\includepdf[pages=1]{capa.pdf}

% \begin{resumo} 
%   
%   Neste artigo descrevemos como alteramos um trabalho previamente desenvolvido
%   de modo a inlcuir novas funcionalidades e requisitos para atender às
%   necessidades de um fluxo contínuo e potencialmente infinito dos dados, as
%   \textit{data stream}. O trabalho que originalmente buscava por agrupamento de
%   dados numa base de dados estática, agora permite realizar essa mesma tarefa
%   sobre um fluxo intermitente dos dados proporcionando a mesma qualidade na
%   precisão dos resultados finais.
%   
% \end{resumo}


\section{Introdução}

As tecnologias de base de dados permitem armazenar grandes volumes de informação
e são de vital importância para organizações, pois constituem o principal
componente de Sistemas de Informação dando suporte a operações de mineração de
dados, consultas complexas, operações de descoberta de conhecimento e
diversos outros tipos de análise de dados.

No entanto, esse modelo tradicional de base de dados finita e pouco dinâmica não
atende às necessidades de uma classe recente de aplicações, em que a informação
é representada como uma sequência (\textit{stream}) de valores potencialmente
ilimitada \cite{Elaine}.

Dentre estas aplicações destacam-se: gerenciamento e monitoramento em
redes de telecomunicação e de dados, monitoramento de tráfego na Internet,
transações financeiras, análise de mercado de ações, sistemas de segurança, e
análise de dados gerados por sensores, tais como medidas atmosféricas, 
medidas em processos industriais, medidas de tráfego em estradas, entre outras.

Essas aplicações capturam intermitentemente dados de eventos que ocorrem no meio
e muitas delas precisam de análises em tempo real para a tomada de decisão de
seus administradores.

Felizmente, a maioria dessas aplicações  não está interessada em extrair
conhecimento de todos os dados já coletados,  mas apenas analisar uma parcela
desses dados, considerando critérios como os  últimos \textit{N} eventos ou os
eventos capturados nos últimos \textit{T}  intervalos de tempo, e, portanto,
análises são viáveis na maioria dos casos reais.

Aplicações que necessitam armazenar um fluxo contínuo de informação em
tempo real armazenam aquilo que chamamos de \textit{data stream}.
Uma \textit{data stream} pode ser caracterizada como uma sequência de itens de
dados contínua, ordenada e potencialmente infinita. Mais especificamente, uma
\textit{data stream} pode ser definida como uma sequência de eventos $e$ em que
cada evento é representado por um conjunto de \textit{E} valores (atributos), tal
que $e_i = (a_1,a_2, \ldots, a_E)$ \cite{Elaine}.

Um conjunto finito de eventos resulta em uma série temporal multidimensional.
Essa pode conter um volume enorme de dados impossível  de armazenar em memória
primária e, portanto, deve ser analisada e posteriormente  armazenada em memória
secundária ou descartada.

Neste trabalho demonstraremos alguns dos resultados obtidos através da adição de
novas funcionalidades sobre o trabalho desenvolvido em \cite{Cordeiro}, cujo
objetivo era desenvolver o algoritmo \textit{Halite} para realizar agrupamentos
em dados estáticos de média a alta dimensionalidade.

Esse algoritmo implementa uma estrutura de dados que  forma o arcabouço dos
algoritmos baseados  na Teoria de Fractais, isto é, uma {\it quad-tree} 
multidimensional. Em estudos  experimentais indicam que o
tempo de construção dessa  estrutura equivale a aproximadamente 70\%  do tempo total
da análise, sendo este  o grande gargalo no processamento \cite{Cordeiro}.

O método proposto tenta implementar nessa estrutura de dados as funcionalidades
necessárias para reduzir seu tempo de contrução e uso desse mesmo
algoritmo na analise de séries temporais de dados semelhantes às citadas
anteriormente.

Nos experimentos realizados obtivemos uma significativa redução nos tempos de
processamento, reduzimos esse tempo em torno de $4$ vezes e mantivemos a mesma
acurácia do algoritmo antigo nos resultados finais. Esses mesmos resultados
foram submetidos ao Simpósio Brasileiro de Banco de Dados (SBBD)  desse ano
resultando em um artigo aceito para apresentação.

%\section{Trabalhos Relacionados}

\section{Indice de atividades desenvolvidas}

\begin{itemize}
  \item Pesquisa e estudo sobre séries temporais
  \item Pesquisa e estudo sobre o método Halite
  \item Desenvolvimento das novas funcionalidades do método Halite
  \item Experimentos
  \item Submissão de artigo ao Simpósio Brasileiro de Banco de Dados
\end{itemize}


\section{Trabalhos relacionados}

Nota-se hoje uma carência de algoritmos de {\bf agrupamento em subespaços} 
voltados à análise de séries temporais multidimensionais,  visto que são raros
os trabalhos que abordam este tema na literatura.

Em \cite{ref9}, é proposta a  
medida {\em SubCMM} ({\it Subspace Cluster Mapping Measure}) para a avaliação de acurácia de resultados, %de agrupamento em subespaços de séries temporais,
a qual detecta erros ocasionados por surgimento, movimentação e divisão do subespaço de cada grupo da série analisada.
Em \cite{ref8}, é proposta a técnica de agrupamento em subespaços {\em StreamPreDeCon}
com foco específico na análise de séries de pacotes de dados em redes de comunicação para detecção de pacotes anômalos. % de dados 

Em \cite{ref3}, 
é proposto um algoritmo incremental de agrupamento em subespaços sobre janelas deslizantes,
o qual inclui um modelo para descrever grupos e detectar mudanças de subgrupos
em séries  temporais em relação a subconjuntos específicos de eventos.
%Com isso, puderam prever algumas possíveis alterações sobre os dados e melhorar tempos de pesquisa sobre estes.
Por fim, em \cite{ref6,ref4} é proposto um algoritmo de mineração em subespaços
que combina o agrupamento baseado em {\it grids} com a mineração de conjuntos freqüêntes em séries temporais. 
%Dessa forma o autor consegue reduzir o uso de memória e tempo de processamento consideravelmente.

Nota-se ainda a existência de um trabalho correlato não referente a agrupamento de dados.
Em \cite{Sousaetal2006} utiliza-se uma {\it quad-tree} multidimensional para analisar séries temporais,
em que também são propostas operações de auto-ajuste da estrutura.
Entretanto, o foco do trabalho é a análise fractal e de dimensão intrínseca dos dados.


\section{Algoritmo Halite} 
\label{sec:halite}

O algoritmo Halite é uma técnica de agrupamento desenvolvido em
\cite{Cordeiro}, o qual permite a busca precisa, rápida e escalável por
agrupamentos em dados estáticos de média a alta dimensionalidade.

Para descrever essa técnica podemos dividi-la em duas principais fases: a
primeira responsável por representar numa estrutrura de dados os eventos
contidos numa \textit{data stream} e a segunda responsável por analisar
essa estrutura em busca de agrupamentos ou \textit{clustering}.

\subsection{Primeira fase}

A fase inicial do algoritmo Halite envolve a construção de uma estrutura de
dados, uma \textit{quad-tree} multidimensional armazenada em
memória primária, referenciada como \textit{Árvore de Contagens}. Essa árvore
representa uma base de dados $^dS$ de $n$ eventos cujo número de atributos de
cada evento é $d$.  Nessa árvore cada  atributo contém um valor numérico real 
normalizado entre o intervalo $[0,1)$ representado num espaço de $d$  dimensões,
ou seja, uma dimensão para  cada atributo da base de eventos.

O número de níveis ou resoluções da árvore $H$ é dado de acordo com a
necessidade da aplicação. O nó raíz (nível 0) representa a base de dados como
um todo e é subdividido em $2^d$ hipercubos no próximo nível (nível 1), nível
em que cada hipercubo apresenta metade do tamanho total do nível anterior. Mais
uma vez, o nível 2 apresenta $2^d$ hipercubos cada um com metade do tamanho dos
hipercubos do nível anterior e assim por diante até o ultimo nível $H-1$.

Nesse contexto, cada hipercubo é representado como uma célula de contagem, sendo
que o nó root não é representado por nenhuma célula única, apenas o nível 1 em
diante contém $2^d$ células. A estrutura da célula é representada
com os seguintes campos: $loc, n, P[d], usedCell, ptr$. O campo $loc$ é um 
identificador único para uma célula em um nível, $n$ é o numero total de pontos
incidentes na célula, $P[d]$ é um vetor que armazena a contagem de pontos
na metade inferior da célula em relação a cada dimensão, $usedCell$ uma variável
booleana e $ptr$ um ponteiro para o próximo nível da árvore.

Na \tree\ um ponto incidente numa célula qualquer do espaço é
contabilizado nas respectivas células incidentes em cada nível. Para identificar
uma célula $a$ em um nível $h$ ($a_h$) devemos observar seu campo $loc$. Na
Figura \ref{fig:figura1} é apresentado em um espaço bidimensional a disposição
dos campos $loc$ de células e seus respectivos níveis.

\begin{figure*}[h]
\centering 
\begin{minipage}{2.85in}
\hspace{12mm}
\includegraphics[scale=0.9]{imagens/imagem1.eps}
%\vspace{5mm}
\caption{Células no espaço $2$-dimensional.}
\label{fig:figura1}
\end{minipage}
\begin{minipage}{2.85in}
\hspace{12mm}
\includegraphics[scale=0.55]{imagens/imagem2.eps}
\caption{Pontos incidentes em células no espaço $2$-dimensional.}
\label{fig:figura2}
\end{minipage}
%\caption{}
%\label{}
\end{figure*}

A célula hachurada está no nível 3, logo para identificá-la nesse nível devemos
conhecer seu respectivo campo $loc$ que nesse caso é igual a $11$. Retornando
ao nível 2 encontramos sua célula mãe também de campo $loc$ igual a $11$ e sua
célula avó com campo $loc$ igual a $01$. Portanto, um ponto incidente sobre o
espaço bidimensional da célula hachurada ($a_3.loc=11$) deve ser contabilizado
em todas as suas células superiores que nesse caso deve ser o caminho na
sequência $a_1.loc=01, a_2.loc=11, a_3.loc=11$.

Para ilustrar essa contagem de pontos, a Figura
\ref{fig:figura2} fornece uma representação de um espaço bidimensional com um
hipercubo de lado unitário. Nessa figura encontramos três pontos na parte
superior do hipercubo, sendo que cada um deles em uma célula do terceiro nível.


Uma representação gráfica  da estrutrura de dados para contar
esses pontos nesse espaço bidimensional é dado na Figura
\ref{fig:figura3}. 

Na Figura \ref{fig:figura3} visualizamos a estrutura de dados contendo um nó
raíz logo no primeiro nível da figura, mais dois nós no nível $2$ logo
abaixo e dois nós no nível $3$. Sabendo-se que temos duas dimensões para
representar os dados ($d=2$) e portanto cada nó apresenta $2^d=4$ células
por nó.

\begin{figure}[ht]
\centering
\includegraphics[width=.7\textwidth]{./imagens/imagem3.eps}
\caption{Estrutura de dados utilizada para representar os pontos}
\label{fig:figura3}
\end{figure}



\subsection{Segunda fase}

A segunda fase do algoritmo \textit{Halite} busca por grupos de objetos
similares em subespaços do espaço original dos dados de entrada. 

%É importante notar que a
Apenas as contagens presentes na \textit{Árvore de contagens} são avaliadas
nesta fase, isto é, não há novas leituras aos objetos de dados de entrada.
O algoritmo %particiona dinamicamente o espaço das regiões a serem analisadas e 
encontra grupos com base na variação de densidade dos dados em subespaços. 
%em que densidades são avaliadas por meio das contagens da \tree.
%Cada nível dessa estrutura, portanto, representa os dados como um \textit{hyper-grid} numa resolução específica.

Em específico, uma análise por convolução é aplicada a cada nível da árvore, por meio de filtros de
Laplace, a fim de localizar concentrações expressivas de pontos no espaço com todas as dimensões,
as quais podem indicar grupos de dados existentes em subespaços do espaço original.
Por ainda não terem sido validados, estes grupos em potencial são chamados de $\beta$-grupos.
Em seguida, são analisados em separado os pontos de cada $\beta$-grupo, projetados em dimensões individuais,
a fim de determinar os subespaços onde a concentração de pontos é mais evidente.
Um teste estatístico é então aplicado para validar cada $\beta$-grupo,
em relação ao seu subespaço de maior evidência,
e os $\beta$-grupos com maior possibilidade de terem sido formados por
tendências reais de agrupamento de dados são identificados e reportados.



\section{Método proposto}

Nesta seção é descrito o novo método \Haliteds\ de agrupamento em subespaços de
séries temporais multidimensionais. O método proposto adiciona três novas 
funcionalidades à \textit{Árvore de contagens} do algoritmo base \Halite\, as
quais são descritas nas subseções seguintes.


\subsection{Inclusão de janelas de eventos}

O algoritmo \Halite\ original obtém os elementos (eventos, em nosso
contexto) de uma base de dados estática, de forma que é necessário ler
sequencialmente os eventos uma única vez até o final e então iniciar o processo
de agrupamento.

Para simular uma aplicação em que os eventos chegam em tempo real para análise
a base de dados estática original foi dividida em algumas partes com número de
eventos aproximadamente iguais de forma a aproximar nossa aplicação daquelas citadas
na introdução. Com isso, nossa aplicação inicia a leitura completa da primeira
parte e já pode iniciar um processo de agrupamento desses dados.

Em nosso contexto, denominamos cada uma dessas partes da base de dados de janela
de eventos. Dependendo da aplicação o critério de escolha dessa
parcela da base de dados ou da \textit{data stream} fica a critério de seus
usuários, os quais podem construí-las à partir dos últimos $N$ eventos
capturados, ou dos eventos capturados a cada intervalo de tempo $T$ e dentre muitas outras
possibilidades. 

Vale ressaltar também que ao iniciar nossa aplicação fica à cargo do usuário
definir o número de janelas que a aplicação deve armazenar para análise de forma
que as janelas mais antigas são descartadas. Por exemplo, se o usuário
especificar $3$ janelas nos parâmetros de inicialização, a aplicação irá ler e
armazenar a primeira janela, ler a segunda janela e armazenar, ler a terceira e
armazenar, e na quarta janela lida os dados da primeira janela serão
sobrescritos e não serão considerados no processo de agrupamento seguinte.

Em vista que as \textit{data streams} são potencialmente infinitas, as janelas,
portanto, limitam a sequência de eventos a serem analisados e possibilitam uma
análise de dados em tempo real, uma vez que, analisamos apenas uma parcela dos
dados capturados.

Com a inclusão das janelas nesse algoritmo também obtivemos a possibilidade de
analisar os dados mais recentes sem a necessidade de reconstruir  toda a
estrutura de dados novamente como no algoritmo original, ou seja, sem
reconstruir a \tree, que é a fase de maior custo
computacional do algoritmo \cite{Cordeiro}.

Dessa forma, o modelo de janelas empregado permitiu simularmos uma
aplicação que recebe eventos intermitentemente para análise sem a necessidade de
realizarmos operações relativamente caras numa base de dados estática e em
constantes atualizações.

Para isso alguma alterações na estrutura de dados descrita na Seção
\ref{sec:halite} foram implementadas, algumas delas referentes aos campos das
células na árvore. O campo $n$ que anteriormente armazenava a contagem de pontos
incidentes em uma célula agora armazena essa mesma contagem, mas leva
em consideração também o número da janela que esses pontos pertencem, ou seja,
esse campo se tranformou em um vetor onde cada posição refere-se a uma janela.

Adicionou-se também mais uma dimensão para o campo $P[i]$ da célula que
anteriormente armazenava a contagem de pontos na metade inferior de uma célula
para uma dimensão $i$. Agora esse campo é uma matriz de duas dimensões cuja
representação é: $P[i][j]$, onde $i$ representa a dimensão e
$j$ a janela correspondente aquele ponto.

O Algoritmo \ref{alg:inserejanela} descreve como é realizado a operação de
inserção de uma janela na árvore. As operações de expansão e contração são
descritas nas seções posteriores.

\begin{algorithm}[H]
\label{alg:inserejanela}
\caption{insereJanela($eventosDaJanela, idDaJanela$)}
\Entrada{Eventos da nova janela e número identificador da nova janela}
\Saida{Árvore de contagem com a nova janela}
\Inicio
{
	Descarta dados da janela mais antiga na árvore\;
	\For{cada evento $e$ da janela}
	{
		\If{$e$ está fora do hiper-cubo representado por $raiz$}
		{
			$Expande(e)$;  // expande a árvore para representar o evento $e$\\
		}
		Insere o evento $e$ na árvore, com referência à janela atual\;
	}
	
	\If{há uma única célula no nível $1$ da árvore}
	{
		$Contrai( \ );$  // contrai a árvore\\
	}

}
\end{algorithm}


\subsection{Análise de dados não normalizados}

No algoritmo \Halite\ original,  um processo de normalização é aplicado aos
atributos dos eventos para transformar os valores reais de entrada  em valores
reais dentro do intervalo $[0, 1)$. Os dados normalizados são então inseridos na
estrutura de dados.

No entanto, pretendemos capturar os atributos de cada evento sem
realizar qualquer tipo de normalização, pois conforme os dados são capturados
esses podem assumir qualquer valor, ou seja, numa eventualidade um atributo de
um evento pode assumir um valor inesperado para a estrutura de dados e assim
invalidar os dados normalizados até então.

Para solucionar esse problema criamos um intervalo com um valor máximo e mínimo
para cada dimensão em que um atributo é relacionado para a estrutura de dados.
Dessa forma, quando um atributo de um evento incide fora desse intervalo a
árvore precisa realizar um procedimento descrito na próxima subseção de
expansão de seu espaço de representação.
Com isso podemos inserir na estrutura de dados os atributos diretamente como
foram capturados sem qualquer normalização dos valores para algum intervalo 
especifico real.
Portanto, esperamos aumentar a precisão dos resultados finais, uma vez que estes
dados não sofrerão qualquer alteração no decorrer da execução da aplicação.

\subsection{Expansão e contração do espaço de representação}

Em vista que os atributos dos eventos assumem valores no intervalo dos números
reais, foi necessário criar para a estrutura de dados um método para ajustar
os intervalos de uma dimensão para capturar os eventos que não incidem sobre
esse intervalo inicial.

Por exemplo, sabendo que cada atributo da \textit{data stream} é associado a uma
dimensão da árvore, quando inserimos a primeira janela de eventos a
própria estrutura de dados se  encarrega de determinar o intervalo inicial que
ela irá adotar para cada dimensão de forma a representar todos os
eventos presentes nessa janela.

Passado essa fase inicial, na chegada da segunda janela de eventos, se a
dimensão $x$ da árvore estiver no intervalo $[1, 3]$ e o próximo
evento conter uma coordenada $x$ igual a $4$ a estrutura deverá realizar
uma operação de expansão para representar esse evento. A estrutura de dados
realiza essa operação até conseguir representar todas as coordenadas do evento
e depois insere o ponto em sua estrutura.

No caso da contração do espaço de representação, essa operação realiza o
procedimento contrário à expansão de forma a eliminar da memória principal
todos os espaços desnecessários para o funcionamento da atividade de
agrupamento.

A seguir é apresentado o Algoritmo \ref{alg:expande} de expansão  do espaço de
representação da estrutura implementada. Note que muitas das mudanças
implementadas estão representadas nesse e nos algoritmos seguintes. Os
identificadores $L_i$ e $H_i$ referem-se respectivamente ao limite mínimo e
máximo da árvore para uma dimensão $i$. São esses valores mínimos e máximos que
se alteram numa expansão ou contração da árvore segundo um fator especificado aqui como $r0$. Esse fator
dobra a cada expansão ou é dividido por dois numa contração, também podemos
compreender ele como a diferença $H_i - L_i$ para todas as dimensões $i$.

Os mesmos identificadores são válidos para o Algoritmo \ref{alg:contrai} cujo
objetivo é reduzir o espaço de representação da estrutura de forma a liberar
regiões de memória insignificantes para o algoritmo.


\begin{algorithm}[h!]
\label{alg:expande}
\caption{Expande($e$)}
\Entrada{Coordenadas $e_i$ de um evento $e$ \ \ \ \ {\bf Saída:} Árvore expandida}
\Inicio
{		
	\If{$e$ está fora do hiper-cubo representado por $raiz$}
	{
		// incrementa o nível inicial de busca por grupos (para a segunda fase)\\
		$nivelInicial = nivelInicial + 1$\;
		$H=H+1$; // incrementa a altura da árvore\\
		\For {cada coordenada $e_i$ do evento $e$}
		{
			$A_i = L_i$; // valor antigo de $L_i$ para uso posterior\\
	  		\uIf{$e_i < L_i$}%é menor do que o valor mínimo da dimensão $i$}
	  		{
				$L_i=L_i-r0$\;
	  		}
	  		\Else
	  		{
	  			$U_i=U_i+r0$\;
	  		}
		}
		
		$r0=r0*2$; \ \
		$aux=raiz$; \ \
		$raiz=new($nó$)$; \ \
		$raiz.ptr=aux$\;
		
		\For{cada dimensão $i$}
		{
			\For{cada janela $j$}
			{
				%{\bf se}
				\uIf{
				$e_i < A_i$
				}
				{
				%{\bf então}
					$raiz.P[i][j]=aux.n[j]$;
				}
				\Else
				{
				%{\bf senão}
					$raiz.P[i][j]=0$;
				}
				%{\bf fim}
			}
		}
		$Expande(e)$; // chamada recursiva para uma possível nova expansão\\	
	}
	
}
\end{algorithm}


\begin{algorithm}[h!]
\label{alg:contrai}
\caption{Contrai( \ )}
%\Entrada{Célula raiz $r$ restante no nodo raíz \ \ \ \ {\bf Saída:} Árvore contraída}
\Saida{Árvore contraída}
\Inicio
{		
	\If{há uma única célula no nível $1$ da árvore $\land$ \\ \ \ \ \ $H>$ valor de $H$ originalmente informado pelo usuário}
	{
		// decrementa o nível inicial de busca por grupos (para a segunda fase)\\
		$nivelInicial = nivelInicial - 1$\;
		$H=H-1$; // decrementa a altura da árvore\\
		$c = $ célula única do nível $1$ da árvore; \ \ 
		$r0=r0/2$\;
		\For{cada dimensão $i$}
		{
			\uIf{$c$ está na metade superior de $raiz$, em relação a $i$}
			{
				$L_i=L_i+r0$\;
			}
			\Else
			{
				$U_i=U_i-r0$\;
			}
		}
		
		\For{cada dimensão $i$}
		{
			\For{cada janela $j$}
			{
				$raiz.P[i][j]=c.P[i][j]$\;
			}
		}
		$aux=raiz$; \ \
		$raiz=c.ptr$; \ \
		$delete(aux)$;
	}
	$Contrai( \ );$  // chamada recursiva para uma possível nova contração\\	
}
\end{algorithm}


\section{Experimentos}

Os experimentos realizados sobre as alterações implementadas neste projeto foram
testadas com duas bases de dados: uma sintética e outra com dados reais sobre
clima.

Basicamente os testes realizados buscavam medir o impacto sobre a acurácia e no
tempo de execução do novo método em relação ao método
antigo. Dessa forma chamaremos o método novo de $Halite_ds$ e o método antigo de
Halite.

Os testes foram realizados numa máquina com Sistema Operacional Linux e 2GB de
memória principal. Ambas as técnicas Halite e \Haliteds foram configuradas
com os valores padrão para seus parâmetros de entrada, H = 4 e  $\alpha=1.0E-10$,
seguindo o que sugere a proposta original do Halite.

\subsection{Experimentos com dados sintéticos}

Para esse experimento geramos uma série sintética de dados com 100 janelas com
aproximadamente 10000 objetos cada, sendo cada um desses com 15 atributos.
Cada janela inclui 5\% de \textit{outliers} e 10 grupos existentes apenas em
subespaços do espaço original de 15 dimensões, com subespaços escolhidos aleatóriamente.

Cada grupo segue uma distribuição normal em seu correspondente subespaço, 
definida com média e desvio padrão aleatórios.
Visto que as janelas devem representar evoluções temporais de uma mesma base de dados,
cada grupo da primeira janela tem seu par correspondente em cada uma das janelas
posteriores, seguindo a mesma média e desvio padrão na geração de dados. Em
específico tilizou-se aqui o mesmo algoritmo de geração de dados
utilizado nos experimentos originais do algoritmo base,
o Algoritmo $6$ em \cite{Cordeiro}.

Os resultados em dados sintéticos são  vistos nas Figuras
\ref{fig:plotSinteticoQ}, \ref{fig:plotSinteticoT} e \ref{fig:plotSinteticoTPartes}.
$M=20$ foi utilizado, ou seja, foram armazenados $20$ janelas de eventos em
memória principal.
%janelas foram sempre mantidas em memória principal.
A Figura \ref{fig:plotSinteticoQ} %fornece subsídios para responder a questão $\bf Q2$.
%É reportada 
reporta a acurácia (percentual) dos resultados %obtidos pelos algoritmos estudados 
em relação à cada janela lida.
Como pode ser visto, a acurácia se mantém similar em todos os casos para ambos os algoritmos.
Para computar a acurácia, 
utilizou-se a mesma estratégia baseada em valores de precisão e revocação
definida na proposta original do algoritmo base,
%Detalhes são encontrados na 
Seção $8.1$ em \cite{Cordeiro}.
%Foca-se agora na questão {\bf Q1}.

A Figura \ref{fig:plotSinteticoT}
reporta os respectivos tempos de processamento. %para cada algoritmo estudado e cada janela.
Como pode ser visto, o novo método \Haliteds\ é em média $4$ vezes mais
eficiente do que o método base \Halite.
Esses resultados são detalhados na
Figura \ref{fig:plotSinteticoTPartes} %detalha estes resultados 
para mostrar 
o tempo gasto em duas fases específicas: %do processamento: 
a construção da \textit{Árvore de contagem} e a busca por grupos.
Como pode ser visto, o tempo de construção da árvore do algoritmo base $Halite$
equivale em média a $89,3\%$ do tempo total da análise, sendo este o grande gargalo no processamento.
Justificam-se assim os ganhos expressivos da nova abordagem proposta.



\subsection{Experimentos com dados reais}

Uma grande série climática real foi estudada  contendo quase um {\it século}
(i.e., anos entre $1917$ e $2010$) de medições diárias de três de atributos climáticos, 
temperaturas máxima e mínima e precipitação de chuva,  efetuadas em uma estação
climática real -- a estação da ESALQ-USP  localizada no município de
Piracicaba\footnote{\ Dados gentilmente fornecidos por colaboradores %especialistas em Meteorologia e em Agrometeorologia
do CEPAGRI-UNICAMP e CPTEC-INPE.}. A série temporal completa contém $33.217$
eventos. Os resultados obtidos são reportados na Figura \ref{fig:plotReal}. 
Janelas mensais e $M=60$ foram utilizados.
É reportado o tempo de processamento para cada algoritmo estudado e cada janela.
Como pode ser visto, o novo método \Haliteds é novamente mais eficiente do que
o método base \Halite, sendo neste caso $4,5$ vezes mais rápido.

\begin{figure*}
\centering 
\begin{minipage}{2.5in}
\includegraphics[scale=0.325]{imagens/plotSinteticoQ.pdf}
\vspace{-2.5mm}
\caption{Acurácia em série sintética.}
\vspace{2.5mm}
\label{fig:plotSinteticoQ}
\end{minipage}
\begin{minipage}{2.5in}
\includegraphics[scale=0.325]{imagens/plotSinteticoT.pdf}
\vspace{-2.5mm}
\caption{Tempo em série sintética.}
\vspace{2.5mm}
\label{fig:plotSinteticoT}
\end{minipage}
\begin{minipage}{2.5in}
\includegraphics[scale=0.325]{imagens/plotSinteticoTPartes.pdf}
\vspace{-2.5mm}
\caption{Tempo em série sintética -- árvore e grupos.}
\label{fig:plotSinteticoTPartes}
\end{minipage}
\begin{minipage}{2.5in}
\includegraphics[scale=0.325]{imagens/plotReal.pdf}
\vspace{-2.5mm}
\caption{Tempo em série climática real.}
\label{fig:plotReal}
\end{minipage}
%\caption{}
%\label{}
\end{figure*}
\vspace{-2.5mm}


\section{Conclusão}

Neste projeto foi proposto um novo algoritmo para agrupamento de dados em
subespaços de séries temporais de média a alta dimensionalidade denominado de
\Haliteds.

A principal contribuição do novo algoritmo \Haliteds\ é permitir a análise de
janelas consecutivas de séries temporais, sem reconstruir,  para cada nova
janela, a estrutura de dados utilizada. Permite-se assim que o conhecimento
prévio obtido dos dados agrupados no passado facilite o agrupamento dos  dados
no presente, diminuindo consideravelmente o custo computacional total da análise.

São  reportados resultados de experimentos realizados numa série temporal
sintética, e também em uma grande série de dados climáticos reais referente a
quase um {\it século} de medições diárias de atributos climáticos.

Para analisar tais séries, o novo algoritmo \Haliteds\  foi em média $4,2$ vezes
mais rápido do que o algoritmo base \Halite, e, ainda assim, obteve
acurácia de resultados similar.

Ao final dos experimentos submetemos um artigo demonstrando esses mesmos
resultados ao Simpósio Brasileiro de Banco de Dados (SBBD)
desse ano resultando num trabalho aceito para apresentação nesse evento.
 \cite{SBBD2014}

 

\bibliographystyle{sbc}
\bibliography{sbc-template}

\end{document}

